(* Code taken from here via Cornell:
 * http://www.cs.cornell.edu/courses/cs3110/2009sp/schedule.html
 * 
 * Binary search tree, each node has value and two children. 
 * 
 * For any node with value x, all the values in the left
 * subtree are smaller than x, and all those in the right
 * subtree are larger than x (using built-in < as comparator).
 *)

type 'a tree = TNode of 'a * 'a tree * 'a tree | TLeaf

let rec contains x = function
    TLeaf -> false
  | TNode (y, l, r) ->
      if x=y then true else if x < y then contains x l else contains x r

let rec add x = function
    TLeaf -> TNode (x, TLeaf, TLeaf) (* When get to leaf, put new node there *)
  | TNode (y, l, r) as t -> (* Recursively search for value *)
      if x=y then t
      else if x > y then TNode (y, l, add x r)
      else (* x < y *) TNode (y, add x l, r)

let rec depth = function
    TLeaf -> 0
  | TNode(_, a, b) -> 1+max (depth a) (depth b)

let rec tree_of_list =
  function
      [] -> TLeaf
    | x :: l ->
	add x (tree_of_list l)

(* fold_inorder f acc t folds the function f over the tree t,
 * going left subtree, current value, right subtree
 *)

let rec fold_inorder f acc t =
  match t with
    TLeaf -> acc
  | TNode(v,l,r) ->
      let acc = fold_inorder f acc l in
      let acc = f acc v in
        fold_inorder f acc r       

(* Check that a binary search tree is ordered: for a node
 * with value x the left subtree has values < x and the
 * right subtree has values > x  *)

(* Returns the minimum value in t, max_int if t is empty
 *)

let findmin_int t =
  let f acc v =
    if v<acc then v else acc
  in fold_inorder f max_int t

(* Returns the maximum value in t, min_int if t is empty
 *)

let findmax_int t =
  let f acc v =
    if v>acc then v else acc
  in fold_inorder f min_int t


(* Check that:
   1. Maximum of the left subtree is less than the current value
   2. Minimum of the right subtree is greater than the current value
   3. Left subtree is a valid BST
   4. Right subtree is a valid BST
   Note: We implicitly require uniqueness of values
   Note: Empty subtrees always satisfy requirements 1 and 2  
 *)

let rec repOk_int t =
  match t with
    TLeaf -> true
  | TNode(v,l,r) ->
      let (lmax,rmin) = (findmax_int l, findmin_int r) in
        lmax < v && v < rmin && repOk_int(l) && repOk_int(r)

let t0 = tree_of_list[3; 5];;
let t1 = tree_of_list [3; 9; 5; 7; 11];;
let t2 = tree_of_list [3; 5; 7; 9; 11];;
let t3 = tree_of_list [1;2;3;4;5;6;7;8;9;10];;

repOk_int t0;;
repOk_int t1;;
repOk_int t2;;
repOk_int t3;;

contains 5 t1;;
contains 6 t1;;
depth t3;;

(* General repOk for any ordered type not just ints *)

(* Returns Some(v), where v is the minimum value in t
   If t is empty, returns None
 *)

let findmin_tree t =
  let f acc v =
    match acc with
      None -> Some(v)
    | Some(x) -> if v<x then Some(v) else acc
  in fold_inorder f None t

(* Returns Some(v), where v is the maximum value in t
   If t is empty, returns None
 *)

let findmax_tree t =
  let f acc v =
    match acc with
      None -> Some(v)
    | Some(x) -> if v>x then Some(v) else acc
  in fold_inorder f None t

(* "Option less than"
 * Returns true if either xo or yo is None
 * Otherwise returns the result of comparing the values inside
 *)

let olt xo yo =
  match (xo,yo) with
    None,_ -> true
  | _,None -> true
  | Some(x),Some(y) -> x < y

(* Check that:
   1. Maximum of the left subtree is less than the current value
   2. Minimum of the right subtree is greater than the current value
   3. Left subtree is a valid BST
   4. Right subtree is a valid BST
   Note: We implicitly require uniqueness of values
   Note: Empty subtrees always satisfy requirements 1 and 2  
 *)

let rec repOk t =
  match t with
    TLeaf -> true
  | TNode(v,l,r) ->
      let (lmax,rmin) = (findmax_tree l, findmin_tree r) in
        (olt lmax (Some(v))) && (olt (Some(v)) rmin) && repOk(l) && repOk(r)

let ta = tree_of_list["c"; "e"];;
let tb = tree_of_list ["c"; "i"; "e"; "g"; "k"];;
let tc = tree_of_list ["c"; "e"; "g"; "i"; "k"];;
let td = tree_of_list ["a";"b";"c";"d";"e";"f";"g";"h";"i";"j"];;

repOk ta;;
repOk tb;;
repOk tc;;
repOk td;;
